#include <bits/stdc++.h>
// 2025/01/29
// tag: 
// Author: Zhang Muen
using namespace std;

int64_t t, k, triangle[2002][2002], presum[2002][2002];

void init(){
    triangle[1][1] = 1;
    for (int i = 2; i <= 2001; i++)
    {
        triangle[i][1] = 1;
        for (int j = 2; j <= i; j++)
        {
            triangle[i][j] = (triangle[i - 1][j] + triangle[i - 1][j - 1]) % k;
        }
    }
}

void presum_init(){
    for (int i = 1; i <= 2001; i++)
        for (int j = 1; j <= 2001; j++)
            presum[i][j] = presum[i - 1][j] + presum[i][j - 1] - presum[i - 1][j - 1] + (!triangle[i][j] && j <= i);
}

signed main()
{
    cin >> t >> k;
    init();
    presum_init();
    while (t--){
        int n, m;
        cin >> n >> m;
        n++, m++;
        cout << presum[n][m] - presum[n][1] - presum[1][m] << endl;
    }
    return 0;
}